package com.it.data_linkedList.leetcode;

/**
 * @author: Coke
 * @DateTime: 2023/06/10/22:15
 * 将数组内两个区间内的有序元素合并
 **/
public class E09LeetCode88 {
    /**
     * 合并两个有序数组
     *
     * @param a: 数组1
     * @param b: 数组2
     * @return int 合并后
     * @DateTime: 2023/6/10 22:39
     * @author: Coke
     */
    public static int[] merge (int[] a, int[] b) {
        int[] k = new int[a.length + b.length];
        int[] k2 = new int[a.length + b.length];
        System.arraycopy(a, 0, k, 0, a.length);
        System.arraycopy(b, 0, k, a.length, b.length);
        return toMerge(k, 0, a.length - 1, a.length, k.length - 1, k2, 0);
    }
    
    /**
     * 执行逻辑
     *
     * @param a:    合并前的数组 两个区间
     * @param i:    左区间起始下标
     * @param iEnd: 左区间结束下标
     * @param j:    右区间起始下标
     * @param jEnd: 右区间结束下标
     * @param b:    合并后的数组
     * @param k:    合并后数组的下标
     * @return int 合并后的数组
     * @DateTime: 2023/6/10 22:39
     * @author: Coke
     */
    private static int[] toMerge (int[] a, int i, int iEnd, int j, int jEnd, int[] b, int k) {
        if (i > iEnd) {
            System.arraycopy(a, j, b, k, jEnd - j + 1);
            return b;
        } else if (j > jEnd) {
            System.arraycopy(a, i, b, k, iEnd - i + 1);
            return b;
        }
        
        if (a[i] < a[j]) {
            b[k] = a[i];
            toMerge(a, i + 1, iEnd, j, jEnd, b, k + 1);
        } else {
            b[k] = a[j];
            toMerge(a, i, iEnd, j + 1, jEnd, b, k + 1);
        }
        return b;
    }
}
